오류 검출 정정

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

오류 검출 정정은 데이터 전송 또는 저장 과정에서 발생하는 오류를 감지하고 수정하는 기술을 의미한다. 고대에는 텍스트의 정확성을 위해 사용되었으며, 현대에는 정보통신 기술의 발전과 함께 이동통신, 인터넷, 디지털 방송 등 다양한 분야에서 필수적으로 활용되고 있다. 오류 정정 부호는 데이터에 중복성을 추가하여 오류를 탐지하고 정정하며, 자동 반복 요청(ARQ), 전방 오류 정정(FEC), 하이브리드 ARQ 방식 등이 존재한다. 오류 검출 방식으로는 반복 부호, 패리티 비트, 체크섬, 순환 중복 검사(CRC), 암호학적 해시 함수 등이 있으며, 오류 정정 부호의 종류는 블록 부호와 컨볼루션 부호로 나뉜다. 오류 검출 정정 기술은 무선 통신, 저장 장치, 우주 통신 등 데이터의 신뢰성이 중요한 분야에서 널리 사용된다.

더 읽어볼만한 페이지

부호 이론 - 해밍 거리
해밍 거리는 길이가 같은 두 문자열에서 서로 다른 기호의 개수를 나타내는 거리 척도로, 아벨 군에서는 벡터의 해밍 무게를 영벡터와의 해밍 거리로 정의하며, 오류 검출, 수정 부호 이론, 정보 이론, 계통학 등에서 활용된다.
부호 이론 - 선형 부호
선형 부호는 유한체 위의 벡터 공간의 부분 공간으로, 데이터 전송 및 오류 정정을 위해 사용되며, 길이, 차원, 최소 거리에 따라 표기되고, 부호어, 생성 행렬, 패리티 검사 행렬 등의 개념을 갖는다.
오류 검출 정정 - 부호 이론
부호 이론은 정보를 효율적으로 표현하고 오류를 감지 및 수정하는 기술을 연구하며, 소스 부호화, 채널 부호화, 암호 부호화 등으로 발전하여 CD, 모뎀, 휴대폰 등 다양한 분야에 응용된다.
오류 검출 정정 - 비터비 알고리즘
비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다.

오류 검출 정정

2. 역사

고대에는 필사자들이 히브리어 성경을 필사하는 대가로 구절(운율의 행)의 수에 따라 돈을 받았다. 성경의 산문 책들은 거의 구절로 쓰이지 않았기 때문에, 필사자들은 작업량을 추정하기 위해 글자 수를 세어야 했다.^[1] 이는 후속 사본 제작과 함께 텍스트 전송의 정확성을 보장하는 데에도 도움이 되었다.^[2]^[3] 서기 7세기에서 10세기 사이에 마소라 학자 그룹은 이를 공식화하고 확장하여 수치 마소라를 만들어 신성한 텍스트의 정확한 복제를 보장했다. 여기에는 행, 절, 책 및 책 그룹의 단어 수, 책의 중간 구절 기록, 단어 사용 통계 및 주석이 포함되었다.^[1] 표준은 토라 두루마리에 단 하나의 글자라도 오류가 있으면 용납될 수 없을 정도로 엄격해졌다.^[4] 그들의 오류 수정 방법의 효과는 기원전 150년에서 기원후 75년 사이에 제작된 사해 문서가 1947년~1956년에 발견되어 수 세기 동안 복사된 정확성으로 입증되었다.^[5]

오류 정정 부호의 현대적 발전은 1947년 리처드 해밍의 공로로 여겨진다.^[6] 해밍 부호에 대한 설명은 클로드 섀넌의 ''통신의 수학적 이론''에 나타났으며^[7], 마르셀 J. E. 골레이에 의해 빠르게 일반화되었다.^[8]

한국에서는 1990년대 이후 정보통신 기술이 급격히 발전하면서 오류 정정 부호 기술이 중요해졌다. 특히, 이동통신, 인터넷, 디지털 방송 등 다양한 분야에서 오류 정정 부호가 필수적으로 사용되고 있다.

2. 1. 한국에서의 발전

한국에서는 1990년대 이후 정보통신 기술이 급격히 발전하면서 오류 정정 부호 기술이 중요해졌다. 특히, 이동통신, 인터넷, 디지털 방송 등 다양한 분야에서 오류 정정 부호가 필수적으로 사용되고 있다.

3. 기본 원리

오류 정정 부호는 데이터에 중복성을 추가하여, 전송 또는 저장 과정에서 발생하는 오류를 탐지하고 정정하는 방식으로 작동한다. 오류 정정 방식은 크게 자동 반복 요청 (ARQ), 전방 오류 정정 (FEC), 그리고 이 둘을 혼합한 하이브리드 ARQ 방식으로 나뉜다.^[10]

일반적으로 오류 검출 및 정정에서는 k 단위 길이(k 비트, k 바이트 등)의 부호를 n = m + k 단위 길이의 부호어로 변환한다. 이를 (n, k) 부호, 또는 부호 형식을 덧붙여 (n, k) ××부호 등으로 부른다(오류 정정 부호 "Error Correction Code"를 특히 '''ECC'''로 약칭한다). 부호어는 최소 해밍 거리가 d > 1, 즉 서로 최소 d 단위가 달라서 이 중복성을 이용하여 순방향 오류 정정이 가능하게 된다. d를 덧붙여 (n, k, d) 부호라고도 한다.

적절한 (n, k, d) 부호는 부호어당 d - 1 단위의 오류를 검출할 수 있으며, [(d - 1) / 2] 단위([ ]는 바닥 함수)의 오류를 정정할 수 있다. d ≦ 2라면, 오류 정정 능력은 [(d - 1) / 2] = 0이 되어 단순한 오류 검출이 된다. 단, 데이터의 손실에 대해서는, 즉 오류 위치가 알려져 있을 때는 d 단위의 손실을 정정할 수 있다. 이를 특히 손실 정정이라고 부른다. 단순한 오류 정정도 최소 1 단위의 손실 정정 능력을 가진다.

예를 들어 (2, 1, 2) 부호인 미러링은,

어느 한쪽에 오류가 발생하면 검출할 수 있지만, 양쪽에 발생하면 검출할 수 없다. (오류 검출 능력 1)
어느 한쪽(어느 쪽인지는 모름)에 오류가 발생하면 정정할 수 없다. (오류 정정 능력 0)
어느 한쪽이 손실되면 정정할 수 있지만, 양쪽이 손실되면 정정할 수 없다. (손실 정정 능력 1)

이 된다. (3, 1, 3) 부호인 삼중 미러링에서는 오류 검출 능력과 손실 정정 능력이 2가 되며, 오류 정정 능력 1도 얻는다.

자동 반복 요청(ARQ)는 오류가 발견되면 재전송을 요청하는 방식이고, 전방 오류 정정(FEC)는 오류 정정 코드를 사용하여 수신측에서 오류를 정정하는 방식이다.

'''자동 반복 요청 (ARQ)'''

자동 반복 요청(ARQ, Automatic Repeat reQuest)은 수신된 데이터에 오류가 있는지 확인하고, 오류가 발견되면 송신 측에 재전송을 요청하는 방식이다.^[10] ARQ는 오류 감지 코드, 승인 및 부정 승인 메시지, 그리고 시간 초과를 활용하여 데이터 전송의 신뢰성을 높인다.^[10] 송신기는 일정 시간 내에 승인을 받지 못하면 데이터를 재전송한다.^[10]

ARQ는 정지-대기 ARQ, Go-Back-N ARQ, 선택적 반복 ARQ와 같은 세 가지 유형의 프로토콜로 나뉜다.^[10] ARQ 방식은 채널 용량이 가변적이거나 알 수 없는 통신 채널에 적합하지만, 재전송으로 인해 지연 시간이 증가할 수 있다.^[10]

ARQ는 ARQ-E 형태로 단파 무선 데이터 링크에서 사용되거나 ARQ-M으로 다중화와 결합되어 사용된다.^[10]

TCP/IP 스택에서 오류 제어는 여러 계층에서 수행된다. 각 이더넷 프레임은 CRC-32 오류 감지를 사용하고, IPv4 헤더에는 체크섬이 포함되어 있다.^[10] TCP는 체크섬을 사용하여 오류를 검출하고, 오류가 있는 패킷은 재전송된다.^[10]

'''전방 오류 정정 (FEC)'''

전방 오류 정정(FEC)은 송신 측에서 오류 정정 코드를 추가하여 데이터를 전송하는 방식이다. 수신 측에서는 이 코드를 이용하여 오류를 정정할 수 있으므로, ARQ 방식과 달리 재전송을 요청할 필요가 없다. 따라서 역채널이 필요 없고 지연 시간이 짧다는 장점이 있다.

FEC는 오류 정정 코드 (ECC)를 사용하여 메시지에 중복 데이터를 추가한다. 오류 정정 코드는 일반적으로 컨볼루션 코드와 블록 코드로 구분된다. 컨볼루션 코드는 비트 단위로 처리되며, 비터비 디코더를 통해 최적의 디코딩이 가능하다. 블록 코드는 블록 단위로 처리되며, 리드-솔로몬 코드가 대표적이다. 이 외에도 터보 코드 및 저밀도 패리티 검사 코드(LDPC)와 같은 효율적인 코드들이 존재한다.

섀넌의 정리는 순방향 오류 정정에서 중요한 정리이며, 특정 오류 확률 또는 신호 대 잡음비(SNR)를 가진 채널에서 안정적인 통신이 가능한 최대 정보율을 설명한다. 이 상한은 채널 용량으로 표현되며, 코드율이 채널 용량보다 작으면 오류 확률을 매우 작게 만들 수 있는 코드가 존재한다.

FEC는 셀룰러 네트워크, 고속 광섬유 통신, Wi-Fi와 같은 물리 계층 통신과 플래시 메모리, 하드 디스크, RAM 등 저장 매체에 사용된다. 특히, 한국의 5G 이동통신, 위성 통신 등에서 주로 사용된다. 다만, FEC는 오류 정정 능력에 한계가 있다.

'''하이브리드 ARQ'''

하이브리드 자동 반복 요청(HARQ)는 자동 반복 요청(ARQ)와 전방 오류 정정(FEC)을 결합한 방식이다.^[10]

하이브리드 ARQ에는 두 가지 기본 방식이 있다.^[10]

메시지는 항상 FEC 패리티 데이터(및 오류 감지 중복)와 함께 전송된다. 수신기는 패리티 정보를 사용하여 메시지를 디코딩하고, 패리티 데이터가 성공적인 디코딩에 충분하지 않은 경우(무결성 검사 실패를 통해 확인) ARQ를 사용하여 재전송을 요청한다.
메시지는 패리티 데이터 없이(오류 감지 정보만 포함하여) 전송된다. 수신기가 오류를 감지하면 ARQ를 사용하여 송신자로부터 FEC 정보를 요청하고 이를 사용하여 원래 메시지를 재구성한다.

후자의 방식은 삭제 채널에서 무율 삭제 코드를 사용할 때 특히 유용하다.

3. 1. 자동 반복 요청 (ARQ)

자동 반복 요청(ARQ, Automatic Repeat reQuest)은 수신된 데이터에 오류가 있는지 확인하고, 오류가 발견되면 송신 측에 재전송을 요청하는 방식이다.^[10] ARQ는 오류 감지 코드, 승인 및 부정 승인 메시지, 그리고 시간 초과를 활용하여 데이터 전송의 신뢰성을 높인다.^[10] 송신기는 일정 시간 내에 승인을 받지 못하면 데이터를 재전송한다.^[10]

ARQ는 정지-대기 ARQ, Go-Back-N ARQ, 선택적 반복 ARQ와 같은 세 가지 유형의 프로토콜로 나뉜다.^[10] ARQ 방식은 채널 용량이 가변적이거나 알 수 없는 통신 채널에 적합하지만, 재전송으로 인해 지연 시간이 증가할 수 있다.^[10]

ARQ는 ARQ-E 형태로 단파 무선 데이터 링크에서 사용되거나 ARQ-M으로 다중화와 결합되어 사용된다.^[10]

TCP/IP 스택에서 오류 제어는 여러 계층에서 수행된다. 각 이더넷 프레임은 CRC-32 오류 감지를 사용하고, IPv4 헤더에는 체크섬이 포함되어 있다.^[10] TCP는 체크섬을 사용하여 오류를 검출하고, 오류가 있는 패킷은 재전송된다.^[10]

3. 2. 전방 오류 정정 (FEC)

전방 오류 정정(FEC)은 송신 측에서 오류 정정 코드를 추가하여 데이터를 전송하는 방식이다. 수신 측에서는 이 코드를 이용하여 오류를 정정할 수 있으므로, ARQ 방식과 달리 재전송을 요청할 필요가 없다. 따라서 역채널이 필요 없고 지연 시간이 짧다는 장점이 있다.

FEC는 오류 정정 코드 (ECC)를 사용하여 메시지에 중복 데이터를 추가한다. 오류 정정 코드는 일반적으로 컨볼루션 코드와 블록 코드로 구분된다. 컨볼루션 코드는 비트 단위로 처리되며, 비터비 디코더를 통해 최적의 디코딩이 가능하다. 블록 코드는 블록 단위로 처리되며, 리드-솔로몬 코드가 대표적이다. 이 외에도 터보 코드 및 저밀도 패리티 검사 코드(LDPC)와 같은 효율적인 코드들이 존재한다.

섀넌의 정리는 순방향 오류 정정에서 중요한 정리이며, 특정 오류 확률 또는 신호 대 잡음비(SNR)를 가진 채널에서 안정적인 통신이 가능한 최대 정보율을 설명한다. 이 상한은 채널 용량으로 표현되며, 코드율이 채널 용량보다 작으면 오류 확률을 매우 작게 만들 수 있는 코드가 존재한다.

FEC는 셀룰러 네트워크, 고속 광섬유 통신, Wi-Fi와 같은 물리 계층 통신과 플래시 메모리, 하드 디스크, RAM 등 저장 매체에 사용된다. 특히, 한국의 5G 이동통신, 위성 통신 등에서 주로 사용된다. 다만, FEC는 오류 정정 능력에 한계가 있다.

3. 3. 하이브리드 ARQ

하이브리드 ARQ는 자동 반복 요청(ARQ)와 전방 오류 정정(FEC)을 결합한 방식이다.^[10]

하이브리드 ARQ에는 두 가지 기본 방식이 있다.^[10]

메시지는 항상 FEC 패리티 데이터(및 오류 감지 중복)와 함께 전송된다. 수신기는 패리티 정보를 사용하여 메시지를 디코딩하고, 패리티 데이터가 성공적인 디코딩에 충분하지 않은 경우(무결성 검사 실패를 통해 확인) ARQ를 사용하여 재전송을 요청한다.
메시지는 패리티 데이터 없이(오류 감지 정보만 포함하여) 전송된다. 수신기가 오류를 감지하면 ARQ를 사용하여 송신자로부터 FEC 정보를 요청하고 이를 사용하여 원래 메시지를 재구성한다.

후자의 방식은 삭제 채널에서 무율 삭제 코드를 사용할 때 특히 유용하다.

4. 오류 검출 방식

오류 검출은 데이터 전송 또는 저장 과정에서 오류가 발생했는지 여부를 확인하는 과정이다. 일반적으로 적절한 해시 함수(또는 구체적으로는, 체크섬, 순환 중복 검사 또는 다른 알고리즘)를 사용하여 구현된다. 해시 함수는 메시지에 고정 길이의 ''태그''를 추가하여 수신자가 태그를 다시 계산하고 제공된 태그와 비교하여 전달된 메시지를 확인할 수 있도록 한다.

다양한 종류의 해시 함수 설계가 존재한다. 그러나 일부는 단순성 또는 특정 종류의 오류(예: 버스트 오류를 감지하는 순환 중복 검사의 성능)를 감지하는 적합성 때문에 특히 널리 사용된다.

반복 부호^[14]^[15]
패리티 부호 (패리티 검사) - 시리얼 통신, RAID-3/4/5/6
** 수직 패리티 검사 (VRC)
** 수평 패리티 검사 (LRC)
정비율 부호 (l out of n 부호)
체크섬
** 그룹 카운트 체크
** Luhn 알고리즘
순회 부호
** 순환 중복 검사 (CRC) - 플로피 디스크, USB
암호학적 해시 함수
전방 오류 정정

4. 1. 반복 부호

반복 부호는 오류 없는 통신을 위해 채널을 통해 비트를 반복하는 코딩 방식이다.^[14]^[15] 전송할 데이터 스트림은 비트 블록으로 나뉘고, 각 블록은 미리 결정된 횟수만큼 반복 전송된다. 예를 들어, 비트 패턴 "1011"을 보내려면 4비트 블록을 세 번 반복하여 "1011 1011 1011"을 생성할 수 있다.

반복 부호는 매우 비효율적이며, 특정 상황에서 오류 검출에 취약하다는 단점이 있지만, 매우 단순하다는 장점이 있어 숫자 방송 전송 등에 사용된다.^[14]^[15]

4. 2. 패리티 비트

패리티 비트는 결과에서 설정된 비트(값이 1인 비트)의 수가 짝수 또는 홀수가 되도록 소스 비트 그룹에 추가되는 비트이다. 이 방식은 출력에서 단일 오류 또는 임의의 다른 홀수(3개, 5개 등)의 오류를 감지하는 데 사용될 수 있는 매우 간단한 방식이다. 짝수 개의 뒤집힌 비트는 데이터에 오류가 있더라도 패리티 비트가 올바르게 보이게 한다.

각 전송된 ''워드''에 추가된 패리티 비트를 가로 중복 검사라고 하며, ''워드'' 스트림 끝에 추가된 패리티 비트를 세로 중복 검사라고 한다. 예를 들어, 일련의 m-비트 ''워드'' 각각에 패리티 비트가 추가되어 해당 워드에 1의 개수가 홀수인지 짝수인지 표시하면, 단일 오류가 있는 모든 워드가 감지된다. 그러나 워드의 어느 위치에 오류가 있는지 알 수 없다. 또한, n개의 워드 각 스트림 후에 패리티 합이 전송되어 가장 최근 그룹에서 전송된 해당 비트 위치에 1의 개수가 홀수인지 짝수인지 표시하는 경우, 오류의 정확한 위치를 결정하고 오류를 수정할 수 있다. 그러나 이 방법은 n개의 워드 각 그룹에 오류가 1개 이하인 경우에만 효과가 보장된다. 더 많은 오류 정정 비트를 사용하면 더 많은 오류를 감지하고 경우에 따라 수정할 수 있다.

패리티 부호(패리티 검사)는 시리얼 통신, RAID-3/4/5/6 등에서 사용된다.

4. 3. 체크섬

체크섬은 고정된 단어 길이(예: 바이트 값)의 메시지 코드 단어의 모듈러 연산 합이다. 의도하지 않은 모든 제로 메시지를 감지하기 위해 전송 전에 합계를 1의 보수 연산을 통해 부정할 수 있다.

체크섬 방식에는 패리티 비트, 검증 숫자, 종단 중복 검사 등이 있다. Damm 알고리즘, Luhn 알고리즘, Verhoeff 알고리즘과 같은 일부 체크섬 방식은 식별 번호를 적거나 기억할 때 사람이 흔히 유발하는 오류를 감지하도록 특별히 설계되었다.

4. 4. 순환 중복 검사 (CRC)

순환 중복 검사(CRC, Cyclic redundancy check)는 컴퓨터 네트워크에서 디지털 데이터의 우발적인 변경을 감지하도록 설계된 안전하지 않은 해시 함수이다. 악의적으로 도입된 오류를 감지하는 데는 적합하지 않다. 이는 입력 데이터를 피제수로 사용하여 유한체에서 다항식 나눗셈에서 제수로 사용되는 ''생성 다항식''의 사양으로 특징지어지며, 나머지가 결과가 된다.

CRC는 버스트 오류를 감지하는 데 적합한 속성을 가지고 있다. 하드웨어로 구현하기가 특히 쉬우므로 컴퓨터 네트워크 및 하드 디스크 드라이브와 같은 저장 장치에서 일반적으로 사용된다.

패리티 비트는 특수한 경우의 1비트 CRC로 볼 수 있다. 순회 부호의 일종으로, 플로피 디스크, USB 등에서 사용된다.

4. 5. 암호학적 해시 함수

암호학적 해시 함수의 출력값은 메시지 다이제스트라고도 하며, 데이터 변경이 우발적인지(예: 전송 오류) 또는 악의적으로 발생했는지에 관계없이 데이터 무결성에 대한 강력한 보장을 제공할 수 있다. 데이터가 수정되면 해시 값이 일치하지 않아 감지될 수 있다. 또한, 주어진 해시 값을 가지고 동일한 해시 값을 생성하는 다른 입력 데이터를 찾는 것은 일반적으로 불가능하다. 공격자가 메시지뿐만 아니라 해시 값도 변경할 수 있는 경우, 추가적인 보안을 위해 키 해시 또는 메시지 인증 코드(MAC)를 사용할 수 있다. 키를 알지 못하면 공격자가 수정된 메시지에 대한 올바른 키 해시 값을 쉽거나 편리하게 계산하는 것이 불가능하다.

암호화 해시 함수는 오류 검출의 대용으로 사용하거나, 변조 방지와 오류 검출을 겸하는 경우가 있다. 변조나 도청이 아닌 노이즈의 영향만을 고려하는 경우, 취약점이 있어도 문제 없다.

MD MD4, MD5, 안전 해시 알고리즘 (SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), SHA-3) 등이 있다.

5. 오류 정정 부호의 종류

오류 정정 부호는 크게 블록 부호와 컨볼루션 부호(convolutional code)로 나뉜다.^[9]

블록 부호는 데이터를 고정된 크기의 블록으로 나누어 처리하는 방식이다.

다중화
** 반복 부호 (repetition code)
* 종횡 패리티
* 해밍 부호 - RAM, RAID-2
* 순회 부호
** 순회 해밍 부호
** 골레이 부호

2원 골레이 부호 (바이너리 골레이 코드/Binary Golay code^영어)

** BCH 부호 - 자동차 무선(43,31), 위성 라디오(63,56)

리드-솔로몬 부호 (RS 부호, RSC)
* CIRC (크로스 인터리브드 리드 솔로몬 코딩/Cross-Interleaved Reed-Solomon Coding^영어) - CD
* 리드 솔로몬 적 부호 (RSP 부호) - DAT

** 차집합 순회 부호

단축화 차집합 순회 부호 - 문자 방송(272,190)

** 파이어 부호 - 하드 디스크
* 희소 그래프 부호
** 터보 부호 (터보 코드/Turbo code^영어)
** 저밀도 패리티 검사 부호 (LDPC) - 10GBASE-T (IEEE 802.3an), Mobile WiMAX (IEEE 802.16e)
컨볼루션 부호(convolutional code)
* Hagelbarger code/Hagelbarger code^영어
* 최대 우도 복호 부호, 비터비 알고리즘(Viterbi Algorithm)

5. 1. 블록 부호

블록 부호는 데이터를 고정된 크기의 블록으로 나누어 처리하는 방식이다.

해밍 부호
리드 솔로몬 부호
BCH 부호
저밀도 패리티 검사 부호 (LDPC)
다중화
** 반복 부호 (repetition code)
* 종횡 패리티
* 해밍 부호 - RAM, RAID-2
* 순회 부호
** 순회 해밍 부호
** 골레이 부호

2원 골레이 부호 (바이너리 골레이 코드/Binary Golay code^영어)

** BCH 부호 - 자동차 무선(43,31), 위성 라디오(63,56)

리드-솔로몬 부호 (RS 부호, RSC)
* CIRC (크로스 인터리브드 리드 솔로몬 코딩/Cross-Interleaved Reed-Solomon Coding^영어) - CD
* 리드 솔로몬 적 부호 (RSP 부호) - DAT

** 차집합 순회 부호

단축화 차집합 순회 부호 - 문자 방송(272,190)

** 파이어 부호 - 하드 디스크
* 희소 그래프 부호
** 터보 부호 (터보 코드/Turbo code^영어)
** 저밀도 패리티 검사 부호 (LDPC) - 10GBASE-T (IEEE 802.3an), Mobile WiMAX (IEEE 802.16e)
컨볼루션 부호/Convolutional code^영어
* Hagelbarger code/Hagelbarger code^영어
* 최대 우도 복호 부호, 비터비 알고리즘/Viterbi Algorithm^영어

해밍 부호는 단일 비트 오류를 정정할 수 있는 간단한 부호이다. RAM, RAID-2 등에 사용된다.

리드-솔로몬 부호 (RS 부호, RSC)는 BCH 부호의 일종이다. 연속적인 오류(버스트 오류)에 강한 특성을 가지고 있으며, CD, DVD 등 저장 매체에서 널리 사용된다.

CIRC (크로스 인터리브드 리드 솔로몬 코딩/Cross-Interleaved Reed-Solomon Coding^영어) - CD
리드 솔로몬 적 부호 (RSP 부호) - DAT

BCH 부호는 자동차 무선(43,31), 위성 라디오(63,56) 등에서 사용되는 오류 정정 부호이다. 리드-솔로몬 부호(RS 부호, RSC)는 BCH 부호의 일종이다.

저밀도 패리티 검사 부호(LDPC)는 10GBASE-T (IEEE 802.3an), Mobile WiMAX (IEEE 802.16e) 등에 사용된다. 매우 낮은 오류율을 제공하며, 5G 이동통신 등 최신 기술에 사용된다.

5. 1. 1. 해밍 부호

해밍 부호는 단일 비트 오류를 정정할 수 있는 간단한 부호이다. RAM, RAID-2 등에 사용된다.

5. 1. 2. 리드-솔로몬 부호

리드-솔로몬 부호 (RS 부호, RSC)는 BCH 부호의 일종이다. 연속적인 오류(버스트 오류)에 강한 특성을 가지고 있으며, CD, DVD 등 저장 매체에서 널리 사용된다.

CIRC (Cross-Interleaved Reed-Solomon Code) - CD
리드 솔로몬 적 부호 (RSP 부호) - DAT

5. 1. 3. BCH 부호

BCH 부호는 자동차 무선(43,31), 위성 라디오(63,56) 등에서 사용되는 오류 정정 부호이다. 리드-솔로몬 부호(RS 부호, RSC)는 BCH 부호의 일종이다.

5. 1. 4. LDPC 부호

저밀도 패리티 검사 부호(LDPC)는 10GBASE-T (IEEE 802.3an), Mobile WiMAX (IEEE 802.16e) 등에 사용된다. 매우 낮은 오류율을 제공하며, 5G 이동통신 등 최신 기술에 사용된다.

5. 2. 컨볼루션 부호

컨볼루션 부호는 데이터를 연속적인 흐름으로 처리하는 방식이다. 최대 우도 복호 부호, 비터비 알고리즘을 사용하여 복호화할 수 있다.

6. 활용 분야

무선 통신, 저장 장치 등 데이터의 신뢰성이 중요한 다양한 분야에서 오류 검출 정정 기술이 활용된다. 특히, 저장 장치 중 CD, DVD, 하드디스크에서는 리드 솔로몬 부호가 사용된다. 낮은 지연 시간이 필요한 응용 분야(예: 전화 통화)는 자동 반복 요청(ARQ)을 사용할 수 없으며, 순방향 오류 수정(FEC)을 사용해야 한다. ARQ 시스템이 오류를 발견하고 재전송할 때쯤이면 재전송된 데이터가 너무 늦게 도착하여 사용할 수 없기 때문이다.

송신자가 전송 직후 정보를 즉시 잊어버리는 응용 분야(예: 대부분의 텔레비전 카메라)는 ARQ를 사용할 수 없으며, 오류가 발생하면 원래 데이터를 더 이상 사용할 수 없으므로 FEC를 사용해야 한다.

ARQ를 사용하는 응용 분야는 반송 채널이 있어야 하며, 반송 채널이 없는 응용 분야는 ARQ를 사용할 수 없다.

매우 낮은 오류율(예: 디지털 자금 이체)이 필요한 응용 분야는 FEC로 수정할 수 없는 오류가 발생할 가능성이 있으므로 ARQ를 사용해야 한다.

신뢰성 및 검사 엔지니어링 또한 오류 정정 코드 이론을 활용한다.

6. 1. 통신

무선 통신 및 저장 장치와 같은 다양한 통신 시스템에서 오류 정정 부호가 활용된다. 특히, 저장 장치 중 CD, DVD, 하드디스크에서는 리드 솔로몬 부호가 사용된다.

일반적인 TCP/IP 스택에서 오류 제어는 여러 계층에서 수행된다.

각 이더넷 프레임은 CRC-32 오류 감지를 사용하며, 오류가 감지된 프레임은 수신 하드웨어에 의해 폐기된다.
IPv4 헤더에는 헤더 내용을 보호하는 체크섬이 포함되어 있어, 잘못된 체크섬이 있는 네트워크 패킷은 네트워크 내에서 또는 수신단에서 삭제된다.
네트워크 라우팅에서 처리 비용을 최소화하고 현재의 링크 계층 기술이 충분한 오류 감지를 제공한다고 가정하여 IPv6 헤더에서는 체크섬이 생략되었다.(RFC 3819 참조)
UDP에는 페이로드 및 주소 정보를 포함하는 선택적 체크섬이 있다. 잘못된 체크섬이 있는 패킷은 네트워크 스택에서 삭제된다. 체크섬은 IPv4에서는 선택 사항이며 IPv6에서는 필수 사항이다. 생략된 경우에는 데이터 링크 계층이 원하는 수준의 오류 보호를 제공한다고 가정한다.
TCP는 페이로드 및 주소 정보를 보호하기 위한 체크섬을 제공한다. 잘못된 체크섬이 있는 패킷은 네트워크 스택에서 삭제되고, ARQ를 사용하여 재전송된다.

통신 중계기 대역폭에 대한 수요는 TV (고화질 텔레비전 포함)와 IP 데이터 전송에 대한 요구에 힘입어 계속 증가하고 있다. 통신 중계기 용량은 선택된 변조 방식과 FEC(전방 오류 정정)에 의해 소모되는 용량의 비율에 의해 결정된다.

6. 2. 저장 장치

저장 장치는 데이터 손실을 방지하기 위해 오류 정정 부호를 사용한다.^[19] 1951년 최초의 자기 테이프 데이터 저장 장치에는 단일 비트 오류를 감지할 수 있는 패리티 트랙이 있었다. 그룹 부호 기록 테이프에 사용된 최적 직사각형 코드는 단일 비트 오류를 감지할 뿐만 아니라 수정하기도 한다. 일부 파일 형식, 특히 아카이브 형식은 손상 및 잘림을 감지하기 위해 체크섬(대부분 CRC32)을 포함하며 손상된 데이터의 일부를 복구하기 위해 중복성 또는 패리티 파일을 사용할 수 있다. 긁힘으로 인한 오류를 수정하기 위해 컴팩트 디스크에는 리드-솔로몬 코드가 사용된다.^[19]

최신 하드 드라이브는 리드-솔로몬 코드를 사용하여 섹터 읽기에서 사소한 오류를 감지하고 수정하며, 오류가 발생한 섹터에서 손상된 데이터를 복구하여 해당 데이터를 예비 섹터에 저장한다.^[20] RAID 시스템은 하드 드라이브가 완전히 고장났을 때 데이터를 복구하기 위해 다양한 오류 정정 기술을 사용한다. ZFS 또는 Btrfs와 같은 파일 시스템과 일부 RAID 구현은 데이터 스크러빙 및 리실버링을 지원하며, 이를 통해 불량 블록을 사용하기 전에 감지하고 (희망적으로) 복구할 수 있다.^[21] 복구된 데이터는 동일한 물리적 위치에 다시 기록되거나, 동일한 하드웨어의 다른 예비 블록에 기록되거나, 교체 하드웨어에 다시 기록될 수 있다.

6. 3. 우주 통신

무선 통신에서 오류 검출 정정 코드의 개발은 행성 간 거리에 따른 신호 전력의 극심한 희석과 우주 탐사선 탑재 전력의 제한으로 인해 심우주 임무의 역사와 밀접하게 연관되어 있다. 초창기 임무에서는 데이터를 부호화하지 않고 전송했지만, 1968년부터 컨볼루션 코드 및 리드-뮬러 코드 형태로 디지털 오류 정정이 구현되었다.^[17] 리드-뮬러 코드는 우주선이 겪는 잡음(노이즈/noise^영어)에 잘 맞았으며, 1969년부터 1977년까지의 마리너 우주선에 구현되어 사용되었다.

1977년에 시작된 보이저 1호 및 보이저 2호 임무는 목성과 토성에서 컬러 영상 및 과학 정보를 전달하도록 설계되었다.^[18] 코딩 요구 사항이 증가했고, 따라서 우주선은 외부 골레이 (24,12,8) 코드와 연접될 수 있는 컨볼루션 코드로 지원되었다. 보이저 2호는 추가적으로 리드-솔로몬 코드의 구현을 지원했다. 연접된 리드-솔로몬-비터비(RSV) 코드는 매우 강력한 오류 정정을 가능하게 했으며, 우주선의 천왕성 및 해왕성까지의 장거리 여정을 가능하게 했다. 1989년 ECC 시스템 업그레이드 후, 두 탐사선 모두 V2 RSV 코딩을 사용했다.

현재 우주 데이터 시스템 자문 위원회는 보이저 2호 RSV 코드와 유사한 성능을 가진 오류 정정 코드의 사용을 최소 기준으로 권장한다. 연접 코드는 우주 임무에서 점점 더 선호도가 떨어지고 있으며, 터보 코드 또는 LDPC 코드와 같은 더 강력한 코드로 대체되고 있다.

수행되는 다양한 종류의 심우주 및 궤도 임무는 모든 경우에 적합한 오류 정정 시스템을 찾는 것이 지속적인 문제임을 시사한다. 지구 근접 임무의 경우, 잡음의 특성이 행성 간 임무의 우주선이 겪는 잡음과 다르다. 또한 우주선이 지구에서 멀어질수록 잡음 보정 문제가 더 어려워진다.

6. 4. 기타

오류 검출 정정은 디지털 방송, 의료 영상, 금융 정보 등 데이터의 신뢰성이 중요한 다양한 분야에서 활용된다. 무선 통신 및 저장 장치 등에 사용된다. 저장 장치 중 CD, DVD, 하드디스크에서는 리드 솔로몬 부호가 사용된다.

참조

_[1] 백과사전 http://www.jewishenc[...]
_[2] 서적 Basics of Biblical Hebrew Grammar: Second Edition https://books.google[...] Zondervan 2009
_[3] 서적 Greek for the Rest of Us: Using Greek Tools Without Mastering Biblical Languages https://books.google[...] Zondervan 2007
_[4] 서적 The Rambam's Mishneh Torah https://www.chabad.o[...] Moznaim Publishing Corporation
_[5] 서적 The Oxford Companion to Archaeology Oxford University Press 1996-12-05
_[6] 간행물 From Error-Correcting Codes through Sphere Packings to Simple Groups The Mathematical Association of America
_[7] 간행물 A Mathematical Theory of Communication
_[8] 간행물 Notes on Digital Coding
_[9] 학술지 Error Detection and Correction: An Introduction 2012-11
_[10] 문서 Reliable Broadband Communication Using a Burst Erasure Correcting Code ACM SIGCOMM 1990
_[11] 서적 2015 Radio and Antenna Days of the Indian Ocean (RADIO) 2022-05-22
_[12] 학술지 IEEE SA - IEEE 802.11ac-2013 https://standards.ie[...] 2022-05-22
_[13] 웹사이트 Transition to Advanced Format 4K Sector Hard Drives {{!}} Seagate US https://www.seagate.[...] 2022-05-22
_[14] 웹사이트 Numbers (and other mysterious) stations http://www.cisquet.n[...] 2012-03-12
_[15] 웹사이트 Mysterious Russian 'Numbers Station' Changes Broadcast After 20 Years http://www.gizmodo.c[...] 2010-08-25
_[16] 학술지 Self-correcting inspection procedure under inspection errors http://www.eng.tau.a[...] IIE Transactions on Quality and Reliability, 34(6), pp. 529-540. 2014-01-10
_[17] 문서 The Development of Turbo and LDPC Codes for Deep-Space Applications Proceedings of the IEEE, Vol. 95, No. 11 2007-11
_[18] 서적 Fundamentals of Error-Correcting Codes https://archive.org/[...] Cambridge University Press
_[19] 서적 Advanced Error Control Techniques for Data Storage Systems https://books.google[...] CRC Press 2018-10-03
_[20] 웹사이트 My Hard Drive Died http://www.myharddri[...]
_[21] 서적 2019 IEEE International Conference on Cluster Computing (CLUSTER) 2019
_[22] 웹사이트 Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite http://www.apmcsta.o[...] Tsinghua Space Center, Tsinghua University, Beijing 2009-02-16
_[23] 잡지 Error Detection and Correction http://www.admin-mag[...] 2014-08-12
_[24] 웹사이트 EDAC Project http://bluesmoke.sou[...] 2014-08-12
_[25] 웹사이트 Documentation/edac.txt https://www.kernel.o[...] kernel.org 2014-08-12
_[26] 문서 http://books.google.[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com